package com.algorithm.lesson_04;

/**
 * 用队列实现栈
 * 
 * @author Administrator
 *
 */
public class TwoQueuesImplStack<T> {
	private Queue<T> dataQueue; // 数据队列
	private Queue<T> helpQueue; // 辅助队列

	public TwoQueuesImplStack() {
		dataQueue = new Queue<T>();
		helpQueue = new Queue<T>();
	}

	/**
	 * 栈是否为空
	 * 
	 * @return
	 */
	public boolean isEmpty() {
		return dataQueue.isEmpty();
	}

	/**
	 * 栈的大小
	 * 
	 * @return
	 */
	public int size() {
		return dataQueue.size();
	}

	/**
	 * 压栈
	 * 
	 * @param value
	 */
	public void push(T value) {
		dataQueue.add(value);
	}

	public T pop() {
		if (dataQueue.isEmpty()) {
			throw new RuntimeException("Your Stack is Empty!");
		}
		// 将dataQueue中除最后一个元素外全部倒入helpQueue中
		while (dataQueue.size() != 1) {
			helpQueue.add(dataQueue.poll());
		}

		T last = dataQueue.poll();

		// 将helpQueue中元素装回dataQueue
		while (!helpQueue.isEmpty()) {
			dataQueue.add(helpQueue.poll());
		}

		return last;
	}

	public T peek() {
		if (dataQueue.isEmpty()) {
			throw new RuntimeException("Your Stack is Empty!");
		}

		// 将dataQueue中除最后一个元素外全部倒入helpQueue中
		while (dataQueue.size() != 1) {
			helpQueue.add(dataQueue.poll());
		}

		// 取出队尾元素并添加到辅助队列
		T last = dataQueue.poll();
		helpQueue.add(last);

		// 将helpQueue中元素装回dataQueue
		while (!helpQueue.isEmpty()) {
			dataQueue.add(helpQueue.poll());
		}

		return last;
	}
}
